/*****************************************************************************
 * 
 * Copyright [2013] [Mervin.Wong]
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 * 
 *       http://www.apache.org/licenses/LICENSE-2.0
 *       
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *  
 *****************************************************************************/
package base.feature;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

import util.D;

import base.Network;

/**
 *@name Path.java
 *@description 
 *@author 王进法<Mervin.Wong>
 *@version 
 *@Date 2013-1-13上午11:18:37
 */
/*********************************************************************************
 *
 *
 *
 **********************************************************************************/

public class Path implements InterfacePath{
	private Network net = null;
	
	public Path(){
		
	}
	public Path(Network net){
		this.net = net;
	}
	public void set(Network net){
		this.net = net;
	}
	public Network get(){
		return this.net;
	}
	/**
	 * 
	 * @name bothNodesPath
	 * @description 计算两个节点间的路径
	 * @param preNodeId
	 * @param postNodeId
	 * @return ArrayList<ArrayList<Number>> path 保存节点的ID
	 */
	@SuppressWarnings("unchecked")
	public ArrayList<Stack<Number>> bothNodesPath(Number preNodeId, Number postNodeId){
		/*
		 * 在此函数中假设节点的id不能为-1
		 */
		ArrayList<Stack<Number>> pathList = new ArrayList<Stack<Number>>();//路径列表
		Stack<Number> tempPath = new Stack<Number>();//存放从源点到当前节点的路径。
		
		Stack<Number> stack = new Stack<Number>();//存储遍历的节点
		stack.push(preNodeId);
		
		Number nodeId = null;
		HashSet<Number> nodeAdjSet = new HashSet<Number>();
		while(!stack.empty()){
			nodeId = stack.pop();
			/**
			 * －1作为标记位，如果栈弹出的是-1，那么路径就回退一个元素
			 */
			if(nodeId.equals(-1)){
				tempPath.pop();
				continue;
			}
			
			tempPath.push(nodeId);
			
			if(nodeId.equals(postNodeId)){
				//输出次路径
				pathList.add((Stack<Number>) tempPath.clone());
				//弹出刚刚压缩栈的nodeId=postNodeId
				tempPath.pop();
				continue;
			}
			nodeAdjSet = this.net.getAdjNodesId(nodeId);//获取此点的邻接点
			stack.push(-1);
			for (Iterator<Number> iterator = nodeAdjSet.iterator(); iterator.hasNext();) {
				nodeId= (Number) iterator.next();
				//过滤掉回路
				//保证路径中的节点是唯一的
				if(!nodeId.equals(preNodeId) && !tempPath.contains(nodeId)){
					stack.push(nodeId);
				}
			}
		}
		return pathList;
	}
	
	/**
	 * @name bothNodesPath
	 * @description 计算两个节点间的路径
	 * @param Network net
	 * @param preNodeId
	 * @param postNodeId
	 * @returnArrayList<Stack<Number>> path 保存节点的ID
	 */
	@SuppressWarnings("unchecked")
	public ArrayList<Stack<Number>> bothNodesPath(Network net,  Number preNodeId, Number postNodeId){
		/*
		 * 在此函数中假设节点的id不能为-1
		 */
		ArrayList<Stack<Number>> pathList = new ArrayList<Stack<Number>>();//路径列表
		Stack<Number> tempPath = new Stack<Number>();//存放从源点到当前节点的路径。
		
		Stack<Number> stack = new Stack<Number>();//存储遍历的节点
		stack.push(preNodeId);
		
		Number nodeId = null;
		HashSet<Number> nodeAdjSet = new HashSet<Number>();
		while(!stack.empty()){
			nodeId = stack.pop();
			/**
			 * －1作为标记位，如果栈弹出的是-1，那么路径就回退一个元素
			 */
			if(nodeId.equals(-1)){
				tempPath.pop();
				continue;
			}
			
			tempPath.push(nodeId);
			
			if(nodeId.equals(postNodeId)){
				//输出次路径
				pathList.add((Stack<Number>) tempPath.clone());
				//弹出刚刚压缩栈的nodeId=postNodeId
				tempPath.pop();
				continue;
			}
			nodeAdjSet = net.getAdjNodesId(nodeId);//获取此点的邻接点
			stack.push(-1);
			for (Iterator<Number> iterator = nodeAdjSet.iterator(); iterator.hasNext();) {
				nodeId= (Number) iterator.next();
				//过滤掉回路
				//保证路径中的节点是唯一的
				if(!nodeId.equals(preNodeId) && !tempPath.contains(nodeId)){
					stack.push(nodeId);
				}
			}
		}
		return pathList;		
	}

	/**
	 * @name bothNodesPathLength
	 * @description 节点间的路径长度
	 * @param preNodeId
	 * @param postNodeId
	 * @return int length
	 */
	public int bothNodesPathLength(Number preNodeId, Number postNodeId){
		
		return 0;
	}
	
	/**
	 * @name bothNodesPathLength
	 * @description 节点间的路径长度
	 * @param Network net
	 * @param preNodeId
	 * @param postNodeId
	 * @return int length
	 */
	public int bothNodesPathLength(Network net,  Number preNodeId, Number postNodeId){
		
		return 0;
	}
	/**
	 * @name bothNodesShortestPath
	 * @descripion 两点之间的最短路径 可能存在多条, 目前只求取一条路径
	 * @param preNodeId
	 * @param postNodeId
	 * @return
	 */
	public ArrayList<HashSet<Number>> bothNodesShortestPath(Number preNodeId, Number postNodeId){
		
		
		return null;
	}
	
	/**
	 * @name bothNodesShortestPath
	 * @descripion 两点之间的最短路径 可能存在多条, 目前只求取一条路径
	 * @param Net
	 * @param preNodeId
	 * @param postNodeId
	 * @return
	 */
	public ArrayList<HashSet<Number>> bothNodesShortestPath(Network net, Number preNodeId, Number postNodeId){
		
		
		return null;
	}
	
	/**
	 * @name netDiameter
	 * @description 网络直径
	 * @return
	 */
	public int netDiameter(){
		return 0;
	}
	

	/**
	 * @name netDiameter
	 * @description 网络直径
	 * @param net
	 * @return
	 */
	public int netDiameter(Network net){
		return 0;
	}
	/**
	 * @name netAvgPathLength 
	 * @description 网络的平均路径长度
	 * @return
	 */
	public float netAvgPathLength(){
		
		return 0;
	}
	
	/**
	 * 
	 * @name netAvgPathLength 
	 * @description 网络的平均路径长度
	 * @param Network net
	 * @return
	 */
	public float netAvgPathLength(Network net){
		
		return 0;
	}
	
	public void Dijkstra(Network net, Number sourceNodeId, Number desNodeId){
		HashMap<Number, Integer> s = new HashMap<Number, Integer>();//顶点集合
		HashMap<Number, Integer> d = new HashMap<Number, Integer>();//到各顶点的最短距离的值
		HashMap<Number, Integer> parent = new HashMap<Number, Integer>();//该顶点的父节点
		
		
	}
	
	public void BellnamFord(Number sourceNodeId){
		
	}
	
}
